NetNews Offline 2/NetNews Offline Volume 2.iso/news/comp/lang/c-part1/7818

Internet Message Format | 1996-08-05 | 5.1 KB

Path: anvil.ugrad.cs.ubc.ca!not-for-mail
From: [e-mail] (Kazimir Kylheku)
Newsgroups: comp.lang.c
Subject: Re: String Encryption
Date: 27 Feb 1996 09:57:15 -0800
Organization: Computer Science, University of B.C., Vancouver, B.C., Canada
Message-ID: <[e-mail]>
References: <[e-mail]> <[e-mail]> <4ghq1u$[e-mail]> <[e-mail]>
NNTP-Posting-Host: anvil.ugrad.cs.ubc.ca

In article <[e-mail]>,
Brian R. Oldham <[e-mail]> wrote:
>
>In article <4ghq1u$[e-mail]>, Matthias Dittrich (matti) writes:
>>[e-mail] (Brett L. Huber) wrote:
>>>Malcolm Smart ([e-mail]) wrote:
>>>> Has anybody out there got any small routines that I can apply to strings
>>>> which will effectively encrypt them (and decrypt!).  It's not a matter of
>>>> state security so it doesn't have to be that secure, just make it
>>>> unreadable.
>>>
>>>It really depends on what level of "unreadability" you want.  Who are
>>>you protecting the data from?  If you aren't protecting a secret, try
>>>"rot13," which translates A->N, B->O, ... Z->M.
>>>
>>>For an introduction to cryptographic techniques, try the sci.crypt FAQ:
>>>http://www.cis.ohio-state.edu/hypertext/faq/bngusenet/sci/crypt/top.html
>>>
>>> ...
>>You also can use the crypt() function (see man 3 crypt).
>>
>>Good luck,
>>Matthias
>>
>Thanks for this information. But for those who like me have only
>mail & news (no web access) it is helpful to find information here.
>
>To comply with Malcolm's caveat, that the encryption routine should
>be a simple one I have found this effective:
>
>for(i=0; i<strlen(buffer); i++)
>    str[i] = ~buffer[i];     /* note the ~ operator */
>
>The ~ operator flips all bits in each byte read rendering the text in
>str unreadable.  Use the same operation to reverse it.

Users who are sophisticated enough to peruse executables with hex viewers are
likely to be able to crack that easily. All you have to do is XOR the entire
file with all 1's, and then look for readable strings.

A better thing would be to at least use a key:

unsigned char *p, *q;
for(p=buffer,q=key;*p;p++,q++) {
    if(!*q)            /* end of key reached---rewind!        */
        q = key;
    *p = (*p * *q) % 131;    /* mult mod prime is invertible        */
}

This assumes that all characters involved are unsigned, and less than 131.
The characters of the buffer are multiplied by the characters of the key.
Since the characters in the key and message are less than 131, they are both
relatively prime to 131. Thus the multiplication is invertible.

To find the inverse function, you have to do a little math:

    C    _= KM (mod P)    (cipher is congruent to key * msg modulo prime)

Given K and C, what is M? To do this, you find the modulo P inverse of K (let's
call it L), and multiply both sides:

    LC    _= LKM (mod P)
    LC    _= M (mod P)

Thus the plaintext is just the product of the inverse and the cipher. You can
precompute the inverses in another array, called "key2", and use the same
function to decrypt (but pass the decrypting key as a parameter).

This scheme is equivalent to a simple substitution cipher, except instead of a
translate table, you have the more restrictive modulo multiplication (which
cannot represent all possible mappings).

By the way, computing the inverse means solving:

    LK    _= 1 (mod P)

    LK - 1  -= 0 (mod P)

    LK - 1  = Pq     (q is integer)

    LK    = Pq + 1

    KL - Pq = 1

This is a linear diophantine equation that you solve to find integral pairs
(L,q). Since you know that there is a unique L modulo 131, you can do a brute
search by looping over q or L.

    L    = (Pq + 1)/K     < P

Suppose that the key for a particular character position is 65 (ascii 'A').
To find the mod 131 inverse, you could just use a brute search for q instead of
bothering to solve the linear diophantine equation.

By hand, I can do:

    GCD(131,65) = GCD(65,1) = 1

Hence, 1 = 131 - 2 * 65,  and thus and L _= -2 (mod 131). In other words,
the inverse is character 129.

Let's try the encryption on the character '0', or 48. First, you encrypt:

65 * 48 % 131    =    3120 % 131    = 107    (i.e. 'k')

Now we take the ciphertext 107 ('k') and try the inverse:

129 * 107 % 131    =    13803 % 131    = 48.

There you have the recovered plaintext.


This is not secure encryption by any means, but it does have some good
ingredients to thwart prying eyes. First of all, the decryption key looks
quite different from the encryption key, and can be dynamically computed from
the encryption key.  Unless the attacker knows his or her number theory basics,
or can spy on/debug running programs, or can successfully apply some
traditional means for cracking a transposition cipher that uses keys, he will
have a hard time. This is also very easy to implement! The same function
encrypts and decrypts (key[n] * char[n] % prime), and computing the inverses
for the decryption key is a cinch even with a brute force search of all the
congruence classes (other than zero mod 131).

The casual Sunday hacker spy armed with a hex editor and a little knowledge
of bit operations little chance.
--